﻿namespace Leetcode.N0031;

public class Solution
{
    public void NextPermutation(int[] nums)
    {
        int findIndex = -1;
        for (int i = nums.Length - 2; i >= 0 && findIndex == -1; i--)
        {
            for (int j = i + 1; j < nums.Length && findIndex == -1; j++)
            {
                if (nums[j] > nums[i] && (j == nums.Length - 1 || nums[j + 1] <= nums[i]))
                {
                    var tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                    findIndex = i;
                }
            }
        }

        if (findIndex == -1)
        {
            nums.Reverse().ToArray().CopyTo(nums, 0);
            return;
        }

        //  冒泡
        for (int i = findIndex + 2; i < nums.Length; i++)
        {
            for (int j = i; j >= findIndex + 2; j--)
            {
                if (nums[j] < nums[j - 1])
                {
                    var tmp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = tmp;
                }
                else
                {
                    break;
                }
            }
        }
    }
}